/*
 * p3670.cpp
 *
 *  Created on: 2013-4-19
 *      Author: zy
 */

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int a[30005];
struct comp
{
	bool operator()(const int &a, const int &b) const
	{
		return a > b;
	}
};
multiset<int> d;
multiset<int, comp> d2;
multiset<int>::iterator it;
multiset<int, comp>::iterator it2;
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	int ans1 = 1;
	d.insert(a[1]);
	for (int i = 2; i <= n; i++)
	{
		it = d.end();
		it--;
		if (a[i] >= (*it))
		{
			ans1++;
			d.insert(a[i]);
		}
		else
		{
			it = d.upper_bound(a[i]);
			d.erase(it);
			d.insert(a[i]);
		}
	}

	int ans2 = 1;
	d2.insert(a[1]);
	for (int i = 2; i <= n; i++)
	{
		it2 = d2.end();
		it2--;
		if (a[i] <= (*it2))
		{
			ans2++;
			d2.insert(a[i]);
		}
		else
		{
			it2 = d2.upper_bound(a[i]);
			d2.erase(it2);
			d2.insert(a[i]);
		}
	}
	printf("%d\n", n - max(ans1, ans2));
	return 0;
}
